package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?
*/

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	var prev *ListNode = nil
	var current *ListNode = head
	for current != nil { //在这里栽过 注意这里是head!=nil，head!=nil表示将整个链表元素遍历完了
		next := current.Next
		current.Next = prev
		prev = current
		current = next
	}

	return prev
}

func main() {
	head := GenerateLinkedList([]int{1, 2, 3})
	revList := reverseList(head)
	fmt.Println(revList)
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev

}
